/**第106题*/
//根据一棵树的中序遍历与后序遍历构造二叉树。 
//
// 注意: 
//你可以假设树中没有重复的元素。 
//
// 例如，给出 
//
// 中序遍历 inorder = [9,3,15,20,7]
//后序遍历 postorder = [9,15,7,20,3] 
//
// 返回如下的二叉树： 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7
// 
// Related Topics 树 深度优先搜索 数组 
// 👍 433 👎 0

package tree.leetcode.editor.cn;

import com.dq.tree.TreeNode;

public class ConstructBinaryTreeFromInorderAndPostorderTraversal {
    public static void main(String[] args) {
        Solution solution = new ConstructBinaryTreeFromInorderAndPostorderTraversal().new Solution();
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        solution.buildTree(inorder,postorder);

    }
        //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {

        return buildTree(postorder, inorder, 0, postorder.length-1, 0, inorder.length-1);
    }
    public TreeNode buildTree(int[] postorder, int[] inorder, int postStart, int postEnd, int inStart, int inEnd) {

        if(postStart>postEnd) return null;
        TreeNode root = new TreeNode(postorder[postEnd]);
        //在中序遍历中查找根节点的index
        int rootIndex = inStart-1;
        while(inorder[++rootIndex]!=postorder[postEnd]);

        //中序新区间为[instart, rootIndex-1], [rootIndex+1,inend]
        //后序新区间为[prestart+1, rootIndex-instart + prestart]
        //[rootIndex-instart + prestart+1,preEnd]

        int rightN = inEnd-rootIndex;
        root.left = buildTree(postorder, inorder,
                postStart, postEnd-rightN-1,
                inStart,rootIndex-1);
        root.right = buildTree(postorder,inorder,
                postEnd-rightN,postEnd-1,
                rootIndex+1,inEnd);

        return root;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}